/*
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'

链接：https://leetcode.cn/problems/intersection-of-two-linked-lists
*/

package LC0160;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

// 链表 双指针 头尾互联
// 让两个指针各自从链表头开始走，走到末尾就指向另外一个链表头
// 如果链表相交，a+c+b b+c+a 两个指针会在交点相遇
// 否则会走到链表尾结点 a+b b+a 都是null
// https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t/
class Solution1 {

    // TODO 如何构造一个相交的链表？

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode pA = headA, pB = headB;

        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
            // 条件表达式 https://blog.csdn.net/qq_29132907/article/details/78413651
        }
        return pA;
    }
    // TODO 时间复杂度?
    // TODO 空间复杂度?
}
